/*
 * Copyright (C) 2013 Google Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "flutter/sky/engine/wtf/PartitionAlloc.h"

#include <string.h>

#ifndef NDEBUG
#include <stdio.h>
#endif

// Two partition pages are used as guard / metadata page so make sure the super
// page size is bigger.
COMPILE_ASSERT(WTF::kPartitionPageSize * 4 <= WTF::kSuperPageSize,
               ok_super_page_size);
COMPILE_ASSERT(!(WTF::kSuperPageSize % WTF::kPartitionPageSize),
               ok_super_page_multiple);
// Four system pages gives us room to hack out a still-guard-paged piece
// of metadata in the middle of a guard partition page.
COMPILE_ASSERT(WTF::kSystemPageSize * 4 <= WTF::kPartitionPageSize,
               ok_partition_page_size);
COMPILE_ASSERT(!(WTF::kPartitionPageSize % WTF::kSystemPageSize),
               ok_partition_page_multiple);
COMPILE_ASSERT(sizeof(WTF::PartitionPage) <= WTF::kPageMetadataSize,
               PartitionPage_not_too_big);
COMPILE_ASSERT(sizeof(WTF::PartitionBucket) <= WTF::kPageMetadataSize,
               PartitionBucket_not_too_big);
COMPILE_ASSERT(sizeof(WTF::PartitionSuperPageExtentEntry) <=
                   WTF::kPageMetadataSize,
               PartitionSuperPageExtentEntry_not_too_big);
COMPILE_ASSERT(WTF::kPageMetadataSize* WTF::kNumPartitionPagesPerSuperPage <=
                   WTF::kSystemPageSize,
               page_metadata_fits_in_hole);
// Check that some of our zanier calculations worked out as expected.
COMPILE_ASSERT(WTF::kGenericSmallestBucket == 8, generic_smallest_bucket);
COMPILE_ASSERT(WTF::kGenericMaxBucketed == 983040, generic_max_bucketed);

namespace WTF {

int PartitionRootBase::gInitializedLock = 0;
bool PartitionRootBase::gInitialized = false;
PartitionPage PartitionRootBase::gSeedPage;
PartitionBucket PartitionRootBase::gPagedBucket;

static size_t partitionBucketNumSystemPages(size_t size) {
  // This works out reasonably for the current bucket sizes of the generic
  // allocator, and the current values of partition page size and constants.
  // Specifically, we have enough room to always pack the slots perfectly into
  // some number of system pages. The only waste is the waste associated with
  // unfaulted pages (i.e. wasted address space).
  // TODO: we end up using a lot of system pages for very small sizes. For
  // example, we'll use 12 system pages for slot size 24. The slot size is
  // so small that the waste would be tiny with just 4, or 1, system pages.
  // Later, we can investigate whether there are anti-fragmentation benefits
  // to using fewer system pages.
  double bestWasteRatio = 1.0f;
  size_t bestPages = 0;
  if (size > kMaxSystemPagesPerSlotSpan * kSystemPageSize) {
    ASSERT(!(size % kSystemPageSize));
    return size / kSystemPageSize;
  }
  ASSERT(size <= kMaxSystemPagesPerSlotSpan * kSystemPageSize);
  for (size_t i = kNumSystemPagesPerPartitionPage - 1;
       i <= kMaxSystemPagesPerSlotSpan; ++i) {
    size_t pageSize = kSystemPageSize * i;
    size_t numSlots = pageSize / size;
    size_t waste = pageSize - (numSlots * size);
    // Leaving a page unfaulted is not free; the page will occupy an empty page
    // table entry. Make a simple attempt to account for that.
    size_t numRemainderPages = i & (kNumSystemPagesPerPartitionPage - 1);
    size_t numUnfaultedPages =
        numRemainderPages
            ? (kNumSystemPagesPerPartitionPage - numRemainderPages)
            : 0;
    waste += sizeof(void*) * numUnfaultedPages;
    double wasteRatio = (double)waste / (double)pageSize;
    if (wasteRatio < bestWasteRatio) {
      bestWasteRatio = wasteRatio;
      bestPages = i;
    }
  }
  ASSERT(bestPages > 0);
  return bestPages;
}

static void parititonAllocBaseInit(PartitionRootBase* root) {
  ASSERT(!root->initialized);

  spinLockLock(&PartitionRootBase::gInitializedLock);
  if (!PartitionRootBase::gInitialized) {
    PartitionRootBase::gInitialized = true;
    // We mark the seed page as free to make sure it is skipped by our
    // logic to find a new active page.
    PartitionRootBase::gPagedBucket.activePagesHead =
        &PartitionRootGeneric::gSeedPage;
  }
  spinLockUnlock(&PartitionRootBase::gInitializedLock);

  root->initialized = true;
  root->totalSizeOfCommittedPages = 0;
  root->totalSizeOfSuperPages = 0;
  root->nextSuperPage = 0;
  root->nextPartitionPage = 0;
  root->nextPartitionPageEnd = 0;
  root->firstExtent = 0;
  root->currentExtent = 0;

  memset(&root->globalEmptyPageRing, '\0', sizeof(root->globalEmptyPageRing));
  root->globalEmptyPageRingIndex = 0;

  // This is a "magic" value so we can test if a root pointer is valid.
  root->invertedSelf = ~reinterpret_cast<uintptr_t>(root);
}

static void partitionBucketInitBase(PartitionBucket* bucket,
                                    PartitionRootBase* root) {
  bucket->activePagesHead = &PartitionRootGeneric::gSeedPage;
  bucket->freePagesHead = 0;
  bucket->numFullPages = 0;
  bucket->numSystemPagesPerSlotSpan =
      partitionBucketNumSystemPages(bucket->slotSize);
}

void partitionAllocInit(PartitionRoot* root,
                        size_t numBuckets,
                        size_t maxAllocation) {
  parititonAllocBaseInit(root);

  root->numBuckets = numBuckets;
  root->maxAllocation = maxAllocation;
  size_t i;
  for (i = 0; i < root->numBuckets; ++i) {
    PartitionBucket* bucket = &root->buckets()[i];
    if (!i)
      bucket->slotSize = kAllocationGranularity;
    else
      bucket->slotSize = i << kBucketShift;
    partitionBucketInitBase(bucket, root);
  }
}

void partitionAllocGenericInit(PartitionRootGeneric* root) {
  parititonAllocBaseInit(root);

  root->lock = 0;

  // Precalculate some shift and mask constants used in the hot path.
  // Example: malloc(41) == 101001 binary.
  // Order is 6 (1 << 6-1)==32 is highest bit set.
  // orderIndex is the next three MSB == 010 == 2.
  // subOrderIndexMask is a mask for the remaining bits == 11 (masking to 01 for
  // the subOrderIndex).
  size_t order;
  for (order = 0; order <= kBitsPerSizet; ++order) {
    size_t orderIndexShift;
    if (order < kGenericNumBucketsPerOrderBits + 1)
      orderIndexShift = 0;
    else
      orderIndexShift = order - (kGenericNumBucketsPerOrderBits + 1);
    root->orderIndexShifts[order] = orderIndexShift;
    size_t subOrderIndexMask;
    if (order == kBitsPerSizet) {
      // This avoids invoking undefined behavior for an excessive shift.
      subOrderIndexMask =
          static_cast<size_t>(-1) >> (kGenericNumBucketsPerOrderBits + 1);
    } else {
      subOrderIndexMask =
          ((1 << order) - 1) >> (kGenericNumBucketsPerOrderBits + 1);
    }
    root->orderSubIndexMasks[order] = subOrderIndexMask;
  }

  // Set up the actual usable buckets first.
  // Note that typical values (i.e. min allocation size of 8) will result in
  // invalid buckets (size==9 etc. or more generally, size is not a multiple
  // of the smallest allocation granularity).
  // We avoid them in the bucket lookup map, but we tolerate them to keep the
  // code simpler and the structures more generic.
  size_t i, j;
  size_t currentSize = kGenericSmallestBucket;
  size_t currentIncrement =
      kGenericSmallestBucket >> kGenericNumBucketsPerOrderBits;
  PartitionBucket* bucket = &root->buckets[0];
  for (i = 0; i < kGenericNumBucketedOrders; ++i) {
    for (j = 0; j < kGenericNumBucketsPerOrder; ++j) {
      bucket->slotSize = currentSize;
      partitionBucketInitBase(bucket, root);
      // Disable invalid buckets so that touching them faults.
      if (currentSize % kGenericSmallestBucket)
        bucket->activePagesHead = 0;
      currentSize += currentIncrement;
      ++bucket;
    }
    currentIncrement <<= 1;
  }
  ASSERT(currentSize == 1 << kGenericMaxBucketedOrder);
  ASSERT(bucket == &root->buckets[0] + (kGenericNumBucketedOrders *
                                        kGenericNumBucketsPerOrder));

  // Then set up the fast size -> bucket lookup table.
  bucket = &root->buckets[0];
  PartitionBucket** bucketPtr = &root->bucketLookups[0];
  for (order = 0; order <= kBitsPerSizet; ++order) {
    for (j = 0; j < kGenericNumBucketsPerOrder; ++j) {
      if (order < kGenericMinBucketedOrder) {
        // Use the bucket of finest granularity for malloc(0) etc.
        *bucketPtr++ = &root->buckets[0];
      } else if (order > kGenericMaxBucketedOrder) {
        *bucketPtr++ = &PartitionRootGeneric::gPagedBucket;
      } else {
        PartitionBucket* validBucket = bucket;
        // Skip over invalid buckets.
        while (validBucket->slotSize % kGenericSmallestBucket)
          validBucket++;
        *bucketPtr++ = validBucket;
        bucket++;
      }
    }
  }
  ASSERT(bucket == &root->buckets[0] + (kGenericNumBucketedOrders *
                                        kGenericNumBucketsPerOrder));
  ASSERT(bucketPtr == &root->bucketLookups[0] +
                          ((kBitsPerSizet + 1) * kGenericNumBucketsPerOrder));
  // And there's one last bucket lookup that will be hit for e.g. malloc(-1),
  // which tries to overflow to a non-existant order.
  *bucketPtr = &PartitionRootGeneric::gPagedBucket;
}

static bool partitionAllocShutdownBucket(PartitionBucket* bucket) {
  // Failure here indicates a memory leak.
  bool noLeaks = !bucket->numFullPages;
  PartitionPage* page = bucket->activePagesHead;
  while (page) {
    if (page->numAllocatedSlots)
      noLeaks = false;
    page = page->nextPage;
  }

  return noLeaks;
}

static void partitionAllocBaseShutdown(PartitionRootBase* root) {
  ASSERT(root->initialized);
  root->initialized = false;

  // Now that we've examined all partition pages in all buckets, it's safe
  // to free all our super pages. We first collect the super page pointers
  // on the stack because some of them are themselves store in super pages.
  char* superPages[kMaxPartitionSize / kSuperPageSize];
  size_t numSuperPages = 0;
  PartitionSuperPageExtentEntry* entry = root->firstExtent;
  while (entry) {
    char* superPage = entry->superPageBase;
    while (superPage != entry->superPagesEnd) {
      superPages[numSuperPages] = superPage;
      numSuperPages++;
      superPage += kSuperPageSize;
    }
    entry = entry->next;
  }
  ASSERT(numSuperPages == root->totalSizeOfSuperPages / kSuperPageSize);
  for (size_t i = 0; i < numSuperPages; ++i)
    freePages(superPages[i], kSuperPageSize);
}

bool partitionAllocShutdown(PartitionRoot* root) {
  bool noLeaks = true;
  size_t i;
  for (i = 0; i < root->numBuckets; ++i) {
    PartitionBucket* bucket = &root->buckets()[i];
    if (!partitionAllocShutdownBucket(bucket))
      noLeaks = false;
  }

  partitionAllocBaseShutdown(root);
  return noLeaks;
}

bool partitionAllocGenericShutdown(PartitionRootGeneric* root) {
  bool noLeaks = true;
  size_t i;
  for (i = 0; i < kGenericNumBucketedOrders * kGenericNumBucketsPerOrder; ++i) {
    PartitionBucket* bucket = &root->buckets[i];
    if (!partitionAllocShutdownBucket(bucket))
      noLeaks = false;
  }
  partitionAllocBaseShutdown(root);
  return noLeaks;
}

static NEVER_INLINE void partitionOutOfMemory() {
  IMMEDIATE_CRASH();
}

static NEVER_INLINE void partitionFull() {
  IMMEDIATE_CRASH();
}

static ALWAYS_INLINE void partitionDecommitSystemPages(PartitionRootBase* root,
                                                       void* addr,
                                                       size_t len) {
  decommitSystemPages(addr, len);
  ASSERT(root->totalSizeOfCommittedPages > len);
  root->totalSizeOfCommittedPages -= len;
}

static ALWAYS_INLINE void partitionRecommitSystemPages(PartitionRootBase* root,
                                                       void* addr,
                                                       size_t len) {
  recommitSystemPages(addr, len);
  root->totalSizeOfCommittedPages += len;
}

static ALWAYS_INLINE void* partitionAllocPartitionPages(
    PartitionRootBase* root,
    int flags,
    size_t numPartitionPages) {
  ASSERT(!(reinterpret_cast<uintptr_t>(root->nextPartitionPage) %
           kPartitionPageSize));
  ASSERT(!(reinterpret_cast<uintptr_t>(root->nextPartitionPageEnd) %
           kPartitionPageSize));
  RELEASE_ASSERT(numPartitionPages <= kNumPartitionPagesPerSuperPage);
  size_t totalSize = kPartitionPageSize * numPartitionPages;
  root->totalSizeOfCommittedPages += totalSize;
  size_t numPartitionPagesLeft =
      (root->nextPartitionPageEnd - root->nextPartitionPage) >>
      kPartitionPageShift;
  if (LIKELY(numPartitionPagesLeft >= numPartitionPages)) {
    // In this case, we can still hand out pages from the current super page
    // allocation.
    char* ret = root->nextPartitionPage;
    root->nextPartitionPage += totalSize;
    return ret;
  }

  // Need a new super page.
  root->totalSizeOfSuperPages += kSuperPageSize;
  if (root->totalSizeOfSuperPages > kMaxPartitionSize)
    partitionFull();
  char* requestedAddress = root->nextSuperPage;
  char* superPage = reinterpret_cast<char*>(
      allocPages(requestedAddress, kSuperPageSize, kSuperPageSize));
  if (UNLIKELY(!superPage)) {
    if (flags & PartitionAllocReturnNull)
      return 0;
    partitionOutOfMemory();
  }
  root->nextSuperPage = superPage + kSuperPageSize;
  char* ret = superPage + kPartitionPageSize;
  root->nextPartitionPage = ret + totalSize;
  root->nextPartitionPageEnd = root->nextSuperPage - kPartitionPageSize;
  // Make the first partition page in the super page a guard page, but leave a
  // hole in the middle.
  // This is where we put page metadata and also a tiny amount of extent
  // metadata.
  setSystemPagesInaccessible(superPage, kSystemPageSize);
  setSystemPagesInaccessible(superPage + (kSystemPageSize * 2),
                             kPartitionPageSize - (kSystemPageSize * 2));
  // Also make the last partition page a guard page.
  setSystemPagesInaccessible(superPage + (kSuperPageSize - kPartitionPageSize),
                             kPartitionPageSize);

  // If we were after a specific address, but didn't get it, assume that
  // the system chose a lousy address and re-randomize the next
  // allocation.
  if (requestedAddress && requestedAddress != superPage)
    root->nextSuperPage = 0;

  // We allocated a new super page so update super page metadata.
  // First check if this is a new extent or not.
  PartitionSuperPageExtentEntry* latestExtent =
      reinterpret_cast<PartitionSuperPageExtentEntry*>(
          partitionSuperPageToMetadataArea(superPage));
  PartitionSuperPageExtentEntry* currentExtent = root->currentExtent;
  bool isNewExtent = (superPage != requestedAddress);
  if (UNLIKELY(isNewExtent)) {
    latestExtent->next = 0;
    if (UNLIKELY(!currentExtent)) {
      root->firstExtent = latestExtent;
    } else {
      ASSERT(currentExtent->superPageBase);
      currentExtent->next = latestExtent;
    }
    root->currentExtent = latestExtent;
    currentExtent = latestExtent;
    currentExtent->superPageBase = superPage;
    currentExtent->superPagesEnd = superPage + kSuperPageSize;
  } else {
    // We allocated next to an existing extent so just nudge the size up a
    // little.
    currentExtent->superPagesEnd += kSuperPageSize;
    ASSERT(ret >= currentExtent->superPageBase &&
           ret < currentExtent->superPagesEnd);
  }
  // By storing the root in every extent metadata object, we have a fast way
  // to go from a pointer within the partition to the root object.
  latestExtent->root = root;

  return ret;
}

static ALWAYS_INLINE void partitionUnusePage(PartitionRootBase* root,
                                             PartitionPage* page) {
  ASSERT(page->bucket->numSystemPagesPerSlotSpan);
  void* addr = partitionPageToPointer(page);
  partitionDecommitSystemPages(
      root, addr, page->bucket->numSystemPagesPerSlotSpan * kSystemPageSize);
}

static ALWAYS_INLINE size_t
partitionBucketSlots(const PartitionBucket* bucket) {
  return (bucket->numSystemPagesPerSlotSpan * kSystemPageSize) /
         bucket->slotSize;
}

static ALWAYS_INLINE size_t
partitionBucketPartitionPages(const PartitionBucket* bucket) {
  return (bucket->numSystemPagesPerSlotSpan +
          (kNumSystemPagesPerPartitionPage - 1)) /
         kNumSystemPagesPerPartitionPage;
}

static ALWAYS_INLINE void partitionPageReset(PartitionPage* page,
                                             PartitionBucket* bucket) {
  ASSERT(page != &PartitionRootGeneric::gSeedPage);
  page->numAllocatedSlots = 0;
  page->numUnprovisionedSlots = partitionBucketSlots(bucket);
  ASSERT(page->numUnprovisionedSlots);
  page->bucket = bucket;
  page->nextPage = 0;
  // NULLing the freelist is not strictly necessary but it makes an ASSERT in
  // partitionPageFillFreelist simpler.
  page->freelistHead = 0;
  page->pageOffset = 0;
  page->freeCacheIndex = -1;
  size_t numPartitionPages = partitionBucketPartitionPages(bucket);
  size_t i;
  char* pageCharPtr = reinterpret_cast<char*>(page);
  for (i = 1; i < numPartitionPages; ++i) {
    pageCharPtr += kPageMetadataSize;
    PartitionPage* secondaryPage =
        reinterpret_cast<PartitionPage*>(pageCharPtr);
    secondaryPage->pageOffset = i;
  }
}

static ALWAYS_INLINE char* partitionPageAllocAndFillFreelist(
    PartitionPage* page) {
  ASSERT(page != &PartitionRootGeneric::gSeedPage);
  size_t numSlots = page->numUnprovisionedSlots;
  ASSERT(numSlots);
  PartitionBucket* bucket = page->bucket;
  // We should only get here when _every_ slot is either used or unprovisioned.
  // (The third state is "on the freelist". If we have a non-empty freelist, we
  // should not get here.)
  ASSERT(numSlots + page->numAllocatedSlots == partitionBucketSlots(bucket));
  // Similarly, make explicitly sure that the freelist is empty.
  ASSERT(!page->freelistHead);
  ASSERT(page->numAllocatedSlots >= 0);

  size_t size = bucket->slotSize;
  char* base = reinterpret_cast<char*>(partitionPageToPointer(page));
  char* returnObject = base + (size * page->numAllocatedSlots);
  char* firstFreelistPointer = returnObject + size;
  char* firstFreelistPointerExtent =
      firstFreelistPointer + sizeof(PartitionFreelistEntry*);
  // Our goal is to fault as few system pages as possible. We calculate the
  // page containing the "end" of the returned slot, and then allow freelist
  // pointers to be written up to the end of that page.
  char* subPageLimit = reinterpret_cast<char*>(
      (reinterpret_cast<uintptr_t>(firstFreelistPointer) +
       kSystemPageOffsetMask) &
      kSystemPageBaseMask);
  char* slotsLimit = returnObject + (size * page->numUnprovisionedSlots);
  char* freelistLimit = subPageLimit;
  if (UNLIKELY(slotsLimit < freelistLimit))
    freelistLimit = slotsLimit;

  size_t numNewFreelistEntries = 0;
  if (LIKELY(firstFreelistPointerExtent <= freelistLimit)) {
    // Only consider used space in the slot span. If we consider wasted
    // space, we may get an off-by-one when a freelist pointer fits in the
    // wasted space, but a slot does not.
    // We know we can fit at least one freelist pointer.
    numNewFreelistEntries = 1;
    // Any further entries require space for the whole slot span.
    numNewFreelistEntries +=
        (freelistLimit - firstFreelistPointerExtent) / size;
  }

  // We always return an object slot -- that's the +1 below.
  // We do not neccessarily create any new freelist entries, because we cross
  // sub page boundaries frequently for large bucket sizes.
  ASSERT(numNewFreelistEntries + 1 <= numSlots);
  numSlots -= (numNewFreelistEntries + 1);
  page->numUnprovisionedSlots = numSlots;
  page->numAllocatedSlots++;

  if (LIKELY(numNewFreelistEntries)) {
    char* freelistPointer = firstFreelistPointer;
    PartitionFreelistEntry* entry =
        reinterpret_cast<PartitionFreelistEntry*>(freelistPointer);
    page->freelistHead = entry;
    while (--numNewFreelistEntries) {
      freelistPointer += size;
      PartitionFreelistEntry* nextEntry =
          reinterpret_cast<PartitionFreelistEntry*>(freelistPointer);
      entry->next = partitionFreelistMask(nextEntry);
      entry = nextEntry;
    }
    entry->next = partitionFreelistMask(0);
  } else {
    page->freelistHead = 0;
  }
  return returnObject;
}

// This helper function scans the active page list for a suitable new active
// page, starting at the passed in page.
// When it finds a suitable new active page (one that has free slots), it is
// set as the new active page and true is returned. If there is no suitable new
// active page, false is returned and the current active page is set to null.
// As potential pages are scanned, they are tidied up according to their state.
// Freed pages are swept on to the free page list and full pages are unlinked
// from any list.
static ALWAYS_INLINE bool partitionSetNewActivePage(PartitionPage* page) {
  if (page == &PartitionRootBase::gSeedPage) {
    ASSERT(!page->nextPage);
    return false;
  }

  PartitionPage* nextPage = 0;
  PartitionBucket* bucket = page->bucket;

  for (; page; page = nextPage) {
    nextPage = page->nextPage;
    ASSERT(page->bucket == bucket);
    ASSERT(page != bucket->freePagesHead);
    ASSERT(!bucket->freePagesHead || page != bucket->freePagesHead->nextPage);

    // Page is usable if it has something on the freelist, or unprovisioned
    // slots that can be turned into a freelist.
    if (LIKELY(page->freelistHead != 0) ||
        LIKELY(page->numUnprovisionedSlots)) {
      bucket->activePagesHead = page;
      return true;
    }

    ASSERT(page->numAllocatedSlots >= 0);
    if (LIKELY(page->numAllocatedSlots == 0)) {
      ASSERT(page->freeCacheIndex == -1);
      // We hit a free page, so shepherd it on to the free page list.
      page->nextPage = bucket->freePagesHead;
      bucket->freePagesHead = page;
    } else {
      // If we get here, we found a full page. Skip over it too, and also
      // tag it as full (via a negative value). We need it tagged so that
      // free'ing can tell, and move it back into the active page list.
      ASSERT(page->numAllocatedSlots ==
             static_cast<int>(partitionBucketSlots(bucket)));
      page->numAllocatedSlots = -page->numAllocatedSlots;
      ++bucket->numFullPages;
      // numFullPages is a uint16_t for efficient packing so guard against
      // overflow to be safe.
      RELEASE_ASSERT(bucket->numFullPages);
      // Not necessary but might help stop accidents.
      page->nextPage = 0;
    }
  }

  bucket->activePagesHead = 0;
  return false;
}

struct PartitionDirectMapExtent {
  size_t mapSize;  // Mapped size, not including guard pages and meta-data.
};

static ALWAYS_INLINE PartitionDirectMapExtent* partitionPageToDirectMapExtent(
    PartitionPage* page) {
  ASSERT(partitionBucketIsDirectMapped(page->bucket));
  return reinterpret_cast<PartitionDirectMapExtent*>(
      reinterpret_cast<char*>(page) + 2 * kPageMetadataSize);
}

static ALWAYS_INLINE void* partitionDirectMap(PartitionRootBase* root,
                                              int flags,
                                              size_t size) {
  size = partitionDirectMapSize(size);

  // Because we need to fake looking like a super page, We need to allocate
  // a bunch of system pages more than "size":
  // - The first few system pages are the partition page in which the super
  // page metadata is stored. We fault just one system page out of a partition
  // page sized clump.
  // - We add a trailing guard page.
  size_t mapSize = size + kPartitionPageSize + kSystemPageSize;
  // Round up to the allocation granularity.
  mapSize += kPageAllocationGranularityOffsetMask;
  mapSize &= kPageAllocationGranularityBaseMask;

  // TODO: we may want to let the operating system place these allocations
  // where it pleases. On 32-bit, this might limit address space
  // fragmentation and on 64-bit, this might have useful savings for TLB
  // and page table overhead.
  // TODO: if upsizing realloc()s are common on large sizes, we could
  // consider over-allocating address space on 64-bit, "just in case".
  // TODO: consider pre-populating page tables (e.g. MAP_POPULATE on Linux,
  // MADV_WILLNEED on POSIX).
  // TODO: these pages will be zero-filled. Consider internalizing an
  // allocZeroed() API so we can avoid a memset() entirely in this case.
  char* ptr = reinterpret_cast<char*>(allocPages(0, mapSize, kSuperPageSize));
  if (!ptr) {
    if (flags & PartitionAllocReturnNull)
      return 0;
    partitionOutOfMemory();
  }
  char* ret = ptr + kPartitionPageSize;
  // TODO: due to all the guard paging, this arrangement creates 4 mappings.
  // We could get it down to three by using read-only for the metadata page,
  // or perhaps two by leaving out the trailing guard page on 64-bit.
  setSystemPagesInaccessible(ptr, kSystemPageSize);
  setSystemPagesInaccessible(ptr + (kSystemPageSize * 2),
                             kPartitionPageSize - (kSystemPageSize * 2));
  setSystemPagesInaccessible(ret + size, kSystemPageSize);

  PartitionSuperPageExtentEntry* extent =
      reinterpret_cast<PartitionSuperPageExtentEntry*>(
          partitionSuperPageToMetadataArea(ptr));
  extent->root = root;
  PartitionPage* page = partitionPointerToPageNoAlignmentCheck(ret);
  PartitionBucket* bucket = reinterpret_cast<PartitionBucket*>(
      reinterpret_cast<char*>(page) + kPageMetadataSize);
  page->freelistHead = 0;
  page->nextPage = 0;
  page->bucket = bucket;
  page->numAllocatedSlots = 1;
  page->numUnprovisionedSlots = 0;
  page->pageOffset = 0;
  page->freeCacheIndex = 0;

  bucket->activePagesHead = 0;
  bucket->freePagesHead = 0;
  bucket->slotSize = size;
  bucket->numSystemPagesPerSlotSpan = 0;
  bucket->numFullPages = 0;

  PartitionDirectMapExtent* mapExtent = partitionPageToDirectMapExtent(page);
  mapExtent->mapSize = mapSize - kPartitionPageSize - kSystemPageSize;

  return ret;
}

static ALWAYS_INLINE void partitionDirectUnmap(PartitionPage* page) {
  size_t unmapSize = partitionPageToDirectMapExtent(page)->mapSize;

  // Add on the size of the trailing guard page and preceeding partition
  // page.
  unmapSize += kPartitionPageSize + kSystemPageSize;

  ASSERT(!(unmapSize & kPageAllocationGranularityOffsetMask));

  char* ptr = reinterpret_cast<char*>(partitionPageToPointer(page));
  // Account for the mapping starting a partition page before the actual
  // allocation address.
  ptr -= kPartitionPageSize;

  freePages(ptr, unmapSize);
}

void* partitionAllocSlowPath(PartitionRootBase* root,
                             int flags,
                             size_t size,
                             PartitionBucket* bucket) {
  // The slow path is called when the freelist is empty.
  ASSERT(!bucket->activePagesHead->freelistHead);

  // For the partitionAllocGeneric API, we have a bunch of buckets marked
  // as special cases. We bounce them through to the slow path so that we
  // can still have a blazing fast hot path due to lack of corner-case
  // branches.
  bool returnNull = flags & PartitionAllocReturnNull;
  if (UNLIKELY(partitionBucketIsDirectMapped(bucket))) {
    ASSERT(size > kGenericMaxBucketed);
    ASSERT(bucket == &PartitionRootBase::gPagedBucket);
    if (size > kGenericMaxDirectMapped) {
      if (returnNull)
        return 0;
      RELEASE_ASSERT(false);
    }
    return partitionDirectMap(root, flags, size);
  }

  // First, look for a usable page in the existing active pages list.
  // Change active page, accepting the current page as a candidate.
  if (LIKELY(partitionSetNewActivePage(bucket->activePagesHead))) {
    PartitionPage* newPage = bucket->activePagesHead;
    if (LIKELY(newPage->freelistHead != 0)) {
      PartitionFreelistEntry* ret = newPage->freelistHead;
      newPage->freelistHead = partitionFreelistMask(ret->next);
      newPage->numAllocatedSlots++;
      return ret;
    }
    ASSERT(newPage->numUnprovisionedSlots);
    return partitionPageAllocAndFillFreelist(newPage);
  }

  // Second, look in our list of freed but reserved pages.
  PartitionPage* newPage = bucket->freePagesHead;
  if (LIKELY(newPage != 0)) {
    ASSERT(newPage != &PartitionRootGeneric::gSeedPage);
    ASSERT(!newPage->freelistHead);
    ASSERT(!newPage->numAllocatedSlots);
    ASSERT(!newPage->numUnprovisionedSlots);
    ASSERT(newPage->freeCacheIndex == -1);
    bucket->freePagesHead = newPage->nextPage;
    void* addr = partitionPageToPointer(newPage);
    partitionRecommitSystemPages(
        root, addr,
        newPage->bucket->numSystemPagesPerSlotSpan * kSystemPageSize);
  } else {
    // Third. If we get here, we need a brand new page.
    size_t numPartitionPages = partitionBucketPartitionPages(bucket);
    void* rawNewPage =
        partitionAllocPartitionPages(root, flags, numPartitionPages);
    if (UNLIKELY(!rawNewPage)) {
      ASSERT(returnNull);
      return 0;
    }
    // Skip the alignment check because it depends on page->bucket, which is not
    // yet set.
    newPage = partitionPointerToPageNoAlignmentCheck(rawNewPage);
  }

  partitionPageReset(newPage, bucket);
  bucket->activePagesHead = newPage;
  return partitionPageAllocAndFillFreelist(newPage);
}

static ALWAYS_INLINE void partitionFreePage(PartitionRootBase* root,
                                            PartitionPage* page) {
  ASSERT(page->freelistHead);
  ASSERT(!page->numAllocatedSlots);
  partitionUnusePage(root, page);
  // We actually leave the freed page in the active list. We'll sweep it on
  // to the free page list when we next walk the active page list. Pulling
  // this trick enables us to use a singly-linked page list for all cases,
  // which is critical in keeping the page metadata structure down to 32
  // bytes in size.
  page->freelistHead = 0;
  page->numUnprovisionedSlots = 0;
}

static ALWAYS_INLINE void partitionRegisterEmptyPage(PartitionPage* page) {
  PartitionRootBase* root = partitionPageToRoot(page);

  // If the page is already registered as empty, give it another life.
  if (page->freeCacheIndex != -1) {
    ASSERT(page->freeCacheIndex >= 0);
    ASSERT(static_cast<unsigned>(page->freeCacheIndex) < kMaxFreeableSpans);
    ASSERT(root->globalEmptyPageRing[page->freeCacheIndex] == page);
    root->globalEmptyPageRing[page->freeCacheIndex] = 0;
  }

  size_t currentIndex = root->globalEmptyPageRingIndex;
  PartitionPage* pageToFree = root->globalEmptyPageRing[currentIndex];
  // The page might well have been re-activated, filled up, etc. before we get
  // around to looking at it here.
  if (pageToFree) {
    ASSERT(pageToFree != &PartitionRootBase::gSeedPage);
    ASSERT(pageToFree->freeCacheIndex >= 0);
    ASSERT(static_cast<unsigned>(pageToFree->freeCacheIndex) <
           kMaxFreeableSpans);
    ASSERT(pageToFree == root->globalEmptyPageRing[pageToFree->freeCacheIndex]);
    if (!pageToFree->numAllocatedSlots && pageToFree->freelistHead) {
      // The page is still empty, and not freed, so _really_ free it.
      partitionFreePage(root, pageToFree);
    }
    pageToFree->freeCacheIndex = -1;
  }

  // We put the empty slot span on our global list of "pages that were once
  // empty". thus providing it a bit of breathing room to get re-used before
  // we really free it. This improves performance, particularly on Mac OS X
  // which has subpar memory management performance.
  root->globalEmptyPageRing[currentIndex] = page;
  page->freeCacheIndex = currentIndex;
  ++currentIndex;
  if (currentIndex == kMaxFreeableSpans)
    currentIndex = 0;
  root->globalEmptyPageRingIndex = currentIndex;
}

void partitionFreeSlowPath(PartitionPage* page) {
  PartitionBucket* bucket = page->bucket;
  ASSERT(page != &PartitionRootGeneric::gSeedPage);
  ASSERT(bucket->activePagesHead != &PartitionRootGeneric::gSeedPage);
  if (LIKELY(page->numAllocatedSlots == 0)) {
    // Page became fully unused.
    if (UNLIKELY(partitionBucketIsDirectMapped(bucket))) {
      partitionDirectUnmap(page);
      return;
    }
    // If it's the current active page, attempt to change it. We'd prefer to
    // leave the page empty as a gentle force towards defragmentation.
    if (LIKELY(page == bucket->activePagesHead) && page->nextPage) {
      if (partitionSetNewActivePage(page->nextPage)) {
        ASSERT(bucket->activePagesHead != page);
        // Link the empty page back in after the new current page, to
        // avoid losing a reference to it.
        // TODO: consider walking the list to link the empty page after
        // all non-empty pages?
        PartitionPage* currentPage = bucket->activePagesHead;
        page->nextPage = currentPage->nextPage;
        currentPage->nextPage = page;
      } else {
        bucket->activePagesHead = page;
        page->nextPage = 0;
      }
    }
    partitionRegisterEmptyPage(page);
  } else {
    // Ensure that the page is full. That's the only valid case if we
    // arrive here.
    ASSERT(page->numAllocatedSlots < 0);
    // A transition of numAllocatedSlots from 0 to -1 is not legal, and
    // likely indicates a double-free.
    RELEASE_ASSERT(page->numAllocatedSlots != -1);
    page->numAllocatedSlots = -page->numAllocatedSlots - 2;
    ASSERT(page->numAllocatedSlots ==
           static_cast<int>(partitionBucketSlots(bucket) - 1));
    // Fully used page became partially used. It must be put back on the
    // non-full page list. Also make it the current page to increase the
    // chances of it being filled up again. The old current page will be
    // the next page.
    page->nextPage = bucket->activePagesHead;
    bucket->activePagesHead = page;
    --bucket->numFullPages;
    // Special case: for a partition page with just a single slot, it may
    // now be empty and we want to run it through the empty logic.
    if (UNLIKELY(page->numAllocatedSlots == 0))
      partitionFreeSlowPath(page);
  }
}

bool partitionReallocDirectMappedInPlace(PartitionRootGeneric* root,
                                         PartitionPage* page,
                                         size_t newSize) {
  ASSERT(partitionBucketIsDirectMapped(page->bucket));

  newSize = partitionCookieSizeAdjustAdd(newSize);

  // Note that the new size might be a bucketed size; this function is called
  // whenever we're reallocating a direct mapped allocation.
  newSize = partitionDirectMapSize(newSize);
  if (newSize < kGenericMinDirectMappedDownsize)
    return false;

  // bucket->slotSize is the current size of the allocation.
  size_t currentSize = page->bucket->slotSize;
  if (newSize == currentSize)
    return true;

  char* charPtr = static_cast<char*>(partitionPageToPointer(page));

  if (newSize < currentSize) {
    size_t mapSize = partitionPageToDirectMapExtent(page)->mapSize;

    // Don't reallocate in-place if new size is less than 80 % of the full
    // map size, to avoid holding on to too much unused address space.
    if ((newSize / kSystemPageSize) * 5 < (mapSize / kSystemPageSize) * 4)
      return false;

    // Shrink by decommitting unneeded pages and making them inaccessible.
    size_t decommitSize = currentSize - newSize;
    partitionDecommitSystemPages(root, charPtr + newSize, decommitSize);
    setSystemPagesInaccessible(charPtr + newSize, decommitSize);
  } else if (newSize <= partitionPageToDirectMapExtent(page)->mapSize) {
    // Grow within the actually allocated memory. Just need to make the
    // pages accessible again.
    size_t recommitSize = newSize - currentSize;
    setSystemPagesAccessible(charPtr + currentSize, recommitSize);
    partitionRecommitSystemPages(root, charPtr + currentSize, recommitSize);

#if ENABLE(ASSERT)
    memset(charPtr + currentSize, kUninitializedByte, recommitSize);
#endif
  } else {
    // We can't perform the realloc in-place.
    // TODO: support this too when possible.
    return false;
  }

#if ENABLE(ASSERT)
  // Write a new trailing cookie.
  partitionCookieWriteValue(charPtr + newSize - kCookieSize);
#endif

  page->bucket->slotSize = newSize;
  return true;
}

void* partitionReallocGeneric(PartitionRootGeneric* root,
                              void* ptr,
                              size_t newSize) {
#if defined(MEMORY_TOOL_REPLACES_ALLOCATOR)
  return realloc(ptr, newSize);
#else
  if (UNLIKELY(!ptr))
    return partitionAllocGeneric(root, newSize);
  if (UNLIKELY(!newSize)) {
    partitionFreeGeneric(root, ptr);
    return 0;
  }

  RELEASE_ASSERT(newSize <= kGenericMaxDirectMapped);

  ASSERT(partitionPointerIsValid(partitionCookieFreePointerAdjust(ptr)));

  PartitionPage* page =
      partitionPointerToPage(partitionCookieFreePointerAdjust(ptr));

  if (UNLIKELY(partitionBucketIsDirectMapped(page->bucket))) {
    // We may be able to perform the realloc in place by changing the
    // accessibility of memory pages and, if reducing the size, decommitting
    // them.
    if (partitionReallocDirectMappedInPlace(root, page, newSize))
      return ptr;
  }

  size_t actualNewSize = partitionAllocActualSize(root, newSize);
  size_t actualOldSize = partitionAllocGetSize(ptr);

  // TODO: note that tcmalloc will "ignore" a downsizing realloc() unless the
  // new size is a significant percentage smaller. We could do the same if we
  // determine it is a win.
  if (actualNewSize == actualOldSize) {
    // Trying to allocate a block of size newSize would give us a block of
    // the same size as the one we've already got, so no point in doing
    // anything here.
    return ptr;
  }

  // This realloc cannot be resized in-place. Sadness.
  void* ret = partitionAllocGeneric(root, newSize);
  size_t copySize = actualOldSize;
  if (newSize < copySize)
    copySize = newSize;

  memcpy(ret, ptr, copySize);
  partitionFreeGeneric(root, ptr);
  return ret;
#endif
}

#ifndef NDEBUG

void partitionDumpStats(const PartitionRoot& root) {
  size_t i;
  size_t totalLive = 0;
  size_t totalResident = 0;
  size_t totalFreeable = 0;
  for (i = 0; i < root.numBuckets; ++i) {
    const PartitionBucket& bucket = root.buckets()[i];
    if (bucket.activePagesHead == &PartitionRootGeneric::gSeedPage &&
        !bucket.freePagesHead && !bucket.numFullPages) {
      // Empty bucket with no freelist or full pages. Skip reporting it.
      continue;
    }
    size_t numFreePages = 0;
    PartitionPage* freePages = bucket.freePagesHead;
    while (freePages) {
      ++numFreePages;
      freePages = freePages->nextPage;
    }
    size_t bucketSlotSize = bucket.slotSize;
    size_t bucketNumSlots = partitionBucketSlots(&bucket);
    size_t bucketUsefulStorage = bucketSlotSize * bucketNumSlots;
    size_t bucketPageSize = bucket.numSystemPagesPerSlotSpan * kSystemPageSize;
    size_t bucketWaste = bucketPageSize - bucketUsefulStorage;
    size_t numActiveBytes = bucket.numFullPages * bucketUsefulStorage;
    size_t numResidentBytes = bucket.numFullPages * bucketPageSize;
    size_t numFreeableBytes = 0;
    size_t numActivePages = 0;
    const PartitionPage* page = bucket.activePagesHead;
    while (page) {
      ASSERT(page != &PartitionRootGeneric::gSeedPage);
      // A page may be on the active list but freed and not yet swept.
      if (!page->freelistHead && !page->numUnprovisionedSlots &&
          !page->numAllocatedSlots) {
        ++numFreePages;
      } else {
        ++numActivePages;
        numActiveBytes += (page->numAllocatedSlots * bucketSlotSize);
        size_t pageBytesResident =
            (bucketNumSlots - page->numUnprovisionedSlots) * bucketSlotSize;
        // Round up to system page size.
        pageBytesResident =
            (pageBytesResident + kSystemPageOffsetMask) & kSystemPageBaseMask;
        numResidentBytes += pageBytesResident;
        if (!page->numAllocatedSlots)
          numFreeableBytes += pageBytesResident;
      }
      page = page->nextPage;
    }
    totalLive += numActiveBytes;
    totalResident += numResidentBytes;
    totalFreeable += numFreeableBytes;
    printf(
        "bucket size %zu (pageSize %zu waste %zu): %zu alloc/%zu commit/%zu "
        "freeable bytes, %zu/%zu/%zu full/active/free pages\n",
        bucketSlotSize, bucketPageSize, bucketWaste, numActiveBytes,
        numResidentBytes, numFreeableBytes,
        static_cast<size_t>(bucket.numFullPages), numActivePages, numFreePages);
  }
  printf("total live: %zu bytes\n", totalLive);
  printf("total resident: %zu bytes\n", totalResident);
  printf("total freeable: %zu bytes\n", totalFreeable);
  fflush(stdout);
}

#endif  // !NDEBUG

}  // namespace WTF
